package arithmetic.LeetCode;

import java.util.ArrayList;
import java.util.List;

class AllPath {


    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        // ,dfs, bfs
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        temp.add(0);
        for (int i = 0; i < graph.length; i++) {
            find(graph, res, 0, temp);
        }
        return res;
    }

    public void find(int[][] graph, List<List<Integer>> res, int index, List<Integer> temp) {
        if (graph[index].length == 0) {
            temp.add(index);
            // 一定要用新的 防止结果相互干扰
            res.add(new ArrayList(temp));
            return;
        }
        // 不需要回退
        for (int i = 0; i < graph[index].length; i++) {
            temp.add(graph[index][i]);
            find(graph, res, graph[index][i], temp);
            if (temp.size() > 0) {
                temp.remove(temp.size() - 1);
            }
        }
    }



}